(1) Field of the Invention
This invention relates to the fields of digital image processing and more particularly to the creation and presentation of three-dimensional (3-D) images on a two dimensional viewing surface.
(2) Description of the Related Art
Since the invention of the stereoscope in the mid 1800s, there have been many successful attempts to make full use of human binocular vision""s ability to combine two separate images, one each obtained by each eye viewing the same scene from slightly different angles, into one image which is perceived as having depth. The mechanics by which the human brain combines two flat images into one image producing the sensation of a three dimensional world is not fully understood. However, many techniques have been developed which deliver, by way of differing processes, slightly different two dimensional images to each eye so as to produce in the brain a perception indistinguishable from that obtained by actually viewing the three dimensional world. These techniques belong generally to two major classes, specifically the autostereoscopic imaging class which produces 3-D images viewable by the unaided eye, and the binocular stereoscopic imaging class which produces 3-D images requiring observers to wear spectacles or viewers. Techniques of the later class can be found in 3-D movies of the 1950s and in recent images returned from the surface of Mars.
Early stereoscopes commonly utilized a specialized device into which was inserted an image comprised of two nearly identical but separate images reproduced side-by-side. Each separate image was created by photographing a scene from one of two slightly different angles. When viewed through the stereoscope, each eye was constrained so as to see only one of the images and the perception of three dimensions was achieved. While this sort of stereoscope does allow for each separate image to be viewed in color and with minimal distortion of the original scene, it possesses the drawback of requiring apparatus to properly constrain each eye""s field of vision and, by so doing, the ability of the viewer to move closer or further, up or down, right or left about the image is severely restricted. Anaglyphs, while generally restricting the creation of 3-D images to those comprised of varying shades of gray, provide the advantage of requiring less obtrusive apparatus for viewing, consist of only one image to be viewed as opposed to two images placed side by side, and allow the viewer to move freely about the image.
An anaglyph is defined as a composite picture printed in two colors that produces a three-dimensional image when viewed through spectacles having lenses of corresponding colors. The best results are obtained when the colors (or, more precisely, hues) used to produce the anaglyph represent orthogonal hues. That is to say, a change in the intensity of one of the hues present at any point on the image does not affect the intensity of the other hue. One typical choice of hues used to produce anaglyphs is that of red and cyan. When a red image is combined with a slightly different cyan image and viewed through glasses having one lens filtering out all but the cyan light and the other lens filtering out all but the red light, the perception of 3-D is accomplished. Because the filters allow only light of one particular wavelength to pass through, the anaglyph is effectively split into two images with each eye seeing a scene depicting the original scene as viewed from one of two slightly different angles.
Barring occlusion, each picture element (hereinafter xe2x80x9cpixelxe2x80x9d) is represented twice in the anaglyph, once in cyan and once in red. The horizontal distance separating the two pixels of differing hue, each of which represents the same pixel in the original image, determines the extent to which the pixel appears in front of or behind the image plane. The xe2x80x9cimage planexe2x80x9d is defined as the plane containing the paper or other medium upon which the anaglyph is displayed. A pixel which rests in three dimensions upon the image plane is unique in that both its red and cyan representations occur at the exact same spot on the anaglyph and, hence, appear to rest in three dimensions upon the image plane. The greater the distance separating the red and cyan representations of a pixel in an anaglyph, the greater the distance the pixel appears to rest in 3-D either above or below the image plane.
Historically, the most common method of producing both stereograms and anaglyphs has been photographic in nature. In such instances, the separate images used to comprise the stereogram or anaglyph are captured photographically. Early 3-D stereograms of cityscapes and anaglyphic movies were created by utilizing two cameras separated by a distance, aimed in the same direction, and operated simultaneously. More recently, satellite images have been used to form stereograms. For instance, stereograms have been assembled from images in the overlap region of two geostationary satellites. With the proliferation of computer technology, it is now possible to describe mathematically, in a computer, objects which need not exist in the natural world, generate realistic two dimensional views from slightly different angles, and combine the views to form stereograms and anaglyphs.
While creation of 3-D images on a computer allows for complete control over the components of the final image, computer-generated 3-D images require considerably more expertise and information to create than do their photographic forbears. One need simply open one""s eyes or point two cameras in any direction to obtain two scenes from slightly different angles. It is not necessary for the perception of depth to acquire a detailed mathematical description of any one object""s relative distance let alone the exact positioning in three dimensions of every single point, comprising every single surface, of every single object which is visible to the observer. In contrast, the creation of a computer generated stereogram or anaglyph does require such detailed information.
While photographic and computer generated anaglyphs differ in the manner by which they are created, the results obtained by either method are quite similar in many important respects. Most importantly, both methods seek to provide each of the viewer""s eyes with a scene that is substantially similar to that which would be observed were the observer to look with unaided vision from a particular vantage point at his surroundings. Photographic anaglyphs produce the sensation of viewing a three dimensional landscape from the vantage point at which the cameras were situated. Computer generated anaglyphs, while able to choose any hypothetical vantage point from which to create the necessary images, must choose only one vantage point.
The restriction imposed by choosing one vantage point imposes both advantages and disadvantages. One primary advantage is that the perception of a three dimensional scene is virtually free of distortion. By mimicking that which the unaided eye would normally observe, the anaglyph produces a sensation quite similar to that produced by natural binocular vision. As discussed, early stereoscopes were comprised of apparatus which constrained the motion of the observer around the image. Early 3-D anaglyphic movies required all observers to be seated some distance from the screen and hence constrained all viewers to a viewing angle approximately perpendicular to the image plane. While producing a quite realistic three dimensional sensation, such applications of 3-D technology have remained interesting gimmicks with little wide spread application.
One primary reason for the limited application of anaglyph technology has been the general requirement that the 3-D image be viewed from a single point approximating the location from which the anaglyph was photographed or from which it was computed. The sensation of 3-D produced when viewing the real world is most pronounced when objects are viewed from a relatively small distance. When viewing far away hills, or even the far side of a room, the brain relies much more on visual cues such as shading, texture, and occlusion to interpret depth information. This reliance on visual cues, separate from that which is strictly binocular in nature, is the result of variations in viewing angles. For example, the amount that each eye must deflect from a parallel orientation fixed on infinity to view a spoon held mere inches from one""s face is quite severe. In addition, the difference between such an angle of deflection and one produced when viewing the same spoon held at arm""s length is likewise quite large. Contrast this with difference in angle existing when viewing a hill that is one mile away and a star which is several hundred million miles away. In the latter instance, the relative difference in viewing angles is quite slight.
Therefore, anaglyphs produced from a single vantage point enjoy their greatest utility when presenting objects that are relatively close to the observer. Unfortunately, such anaglyphs are constrained to a relatively small field of view. Were one to stare off center or at the periphery of an anaglyph, as opposed to a viewing angle perpendicular to the image plane, the image appears greatly distorted. Therefore, an unfortunate paradox arises. Anaglyphs of far away objects allow for a greater field of view and appear less distorted when viewed from slightly different angles but the 3-D effect is diminished from the outset owing to the large distance between the objects and the viewer. Conversely, objects close to the viewer appear in very realistic 3-D but the field of view is diminished greatly and even slight movements about the anaglyph result in large distortions.
One subset of three dimensional objects that in theory would benefit most from the advantages of traditional anaglyph technology while suffering most from its disadvantages is the set consisting of planetary surfaces. Traditionally, such surfaces have been portrayed in two dimensions in the familiar guise of maps. In addition, planetary surfaces have for some time been recreated in true three dimensional form as globes, but suffer from problems related to the inability to store, reproduce, transmit, and conveniently bundle a spherical object in the same manner as one can a flat image. Furthermore, as the Encyclopedia Americana observes, xe2x80x9cThe spherical surface of a globe cannot be flattened into a map without stretching or tearing; therefore, distortion occurs in the process.xe2x80x9d This simple premise, long considered to be an unavoidable fact, has given rise to myriad map projections over the millennia. Map projections such as the mercator, plate carxc3xa9e, and others all seek to derive maximum utility when displaying map data while minimizing the inevitable distortion.
While different projections address differently the problems of longitudinal and latitudinal distortion, they do not generally make any attempt to incorporate elevation data. Much as the human eye can gather depth information from visual cues, many maps incorporate colors, shaded relief, and contour lines of equal elevation to transmit course elevation data. Shaded relief illustrates the roughness of terrain and changes in elevation but cannot show actual elevation. Contour lines can show the horizontal shape of vertical features and the elevation values of the quantized contour lines, but do not show the actual vertical shape. However, to see the actual shape of a planetary surface, some method of displaying the surface in true 3-D is required.
The related art in anaglyph production allows one to overcome the problems of distortion associated with flattening a spherical globe onto a two dimensional map. It is quite possible to compute two slightly different views of a spherical surface as they would appear to an unaided observer. However, such an anaglyph, while accurately representing the three dimensional surface of a planet with little or no distortion, would be of relatively less use as a map. As discussed, one primary drawback of a traditional anaglyph is the necessity of viewing the final image from one and only one vantage point, the point in space from which the original images were photographed or computed. Maps are customarily viewed from a variety of vantage points. Large scale political maps may be viewed from a greater distance so as to observe relatively large land masses, boundaries, and the interplay of point, line, and area data. Before battle, Napoleon customarily placed his maps on the floor, alternatingly standing above them and crawling over them. Were a traditional anaglyph used to produce a map in accordance with the related art, such movement by the observer would be impossible. Because the map would be projected and computed as seen from a singular vantage point, movement by the viewer away from the intended viewing point in space would cause gross distortion.
A partial solution to these problems prevalent in the anaglyphic display of map data was revealed in an article by W. Pichel [Bulletin of the American Meteorological Society, Vol. 54, No. 7, July 1973, pp. 688-691]. Pichel created an algorithm for creating stereo pair images from satellite images one of which was comprised of the visible spectrum, the other containing infrared (IR) data. On a line-by-line basis, the IR data was used as a pseudo height indicator for each corresponding pixel in the visible image. As Pichel explained:
Thus a simple computer algorithm treats coincident scan lines of visual channel data and the equivalent IR data that have been transformed into a scan profile of height levels. The output is a visual channel stereo line pair in which the visual data are displayed with no change in position for elements at zero height level, but in which elements at other levels are shifted in position. A picture element with height level xe2x80x9chxe2x80x9d is displaced from its original position by xe2x80x9chxe2x80x9d spots to the right in the left stereo view and xe2x80x9chxe2x80x9d spots to the left in the right stereo view . . .
A dilemma is encountered where two picture elements are competing for the same location. At present the higher element is retained and the lower element is discarded. In other instances gaps may exist after the displacement process is completed.
While producing pleasing images which, if georeferenced, could be considered as maps, this methodology suffers from four drawbacks. First, elevations appear relatively correct but absolutely incorrect. Clouds of lower temperature, and hence higher elevation, will appear more displaced than clouds of higher temperature and will thus appear to be at a higher elevation everywhere on the map. However, the apparent difference in elevation between a pixel at level five and a pixel at level ten will not appear to be the same difference in elevation as between a pixel at level ten and a pixel at level fifteen. In each case, the difference in elevation is five units but the simple algorithm of pixel displacement employed produces nonlinear viewing effects. This concern is minimized when one considers that the underlying elevation data is itself not considered to be absolutely correct as the relationship between elevation and temperature in the atmosphere is not perfectly linear. Therefore, the elevation levels computed were accepted as rough estimates from the outset.
Second, the creation of a stereogram produces two images side by side. As such, the same pixel appearing in each image is separated on average by the approximate width of either image. Therefore, either with special viewing apparatus or without, the ability of the observer to move around the image is curtailed. Third, this simple algorithm, by displacing all of the pixels in either computed image either all to the left or all to the right, features appear either uniformly in front of or behind the image plane. Thus, a map computed using this algorithm could not have both mountains rising from the image plane and canyons descending beneath it. The entire surface would have to appear either entirely below or entirely above the image plane.
The fourth and most difficult problem to overcome is the likely presence of gaps resulting from the displacement process. The simplest algorithms for reprojecting image data involve mapping each pixel on the original image to a location on the final image. A simple forward looking algorithm such as the one presented above possesses the attribute of being very simple and fast to implement. Unfortunately, because several pixels in the original image may map to the same location in the final image, there are likely to exist gaps in the final image consisting of pixel locations onto which no pixels were mapped. In such cases, smoothing algorithms can be employed which produce values for the missing pixels while masking the loss of data that produced the problem. The alternative, constructing a process hereby every pixel in the final image is assigned a value ascertained by working backwards t o determine which pixel at what elevation in the original image would ultimately appear to exist at the location being considered, can be prohibitively costly in terms of both complexity and computing speed.
Interestingly, in such a process, each pixel is projected in accordance with its own unique vantage point. Thus, instead of using a single vantage point for the entire image, there exist as many vantage points as there are pixel s in the original image. As mentioned, one advantage of having a single vantage point for viewing a stereoscopic or anaglyphic image is that, when viewed from that point, there is virtually no distortion present over the entire image. Following the method described above, displacement of each pixel is computed without any regard to a single vantage point governing the projection of the image as a whole. Such a method possesses unique properties when employed to render maps.
A single point represented by horizontally displaced red and cyan points computed and viewed from directly above will not produce either latitudinal or longitudinal distortion. Any distortion present must arise from the difference between the angle at which the observer views the red and cyan and pixels and nadir. Therefore, pixels appearing immediately horizontally or vertically adjacent to the point directly in front of the observer will appear slightly distorted. Distortion increases as the observer""s gaze extends radially from nadir. Because distortion is directly proportional to the radial aperture of the area being viewed by the observer, relatively small areas will appear to be virtually free of distortion. In order to view larger areas, the observer must move backwards to increase the field of view. In so doing, the maximum angular distortion present in the larger field of view is reduced to a threshold approximating that of the smaller area viewed from a closer vantage point. This results from the fact that viewing a larger area from the same distance as a smaller area requires a greater deflection of the viewing angle. However, the angle of deflection is proportional to the viewing distance and thus the viewer may move back, decreasing the deflection of the viewing angle to that experienced closer in.
The present invention seeks to maximize the utility derived from projecting map data using multiple vantage points while minimizing or eliminating the obstacles present in the related art. As mentioned, traditional anaglyphic techniques utilizing one vantage point permit viewing of the image from one point with virtually no distortion, but result in large amounts of distortion when the viewer moves even slightly around the image. The present invention projects each pixel individually. One notable difference between the present invention and the related art is that while each pixel is projected from a different vantage point, each pixel is projected as though viewed from directly above by an observer who is everywhere located the same distance above the image and whose eyes are separated everywhere by the same distance. The related art, by virtue of its simple, non-linear computation of displacement, and hence perceived elevation, computed each point a having either a different viewing distance, a different eye separation, or both with the result that the vertical scale is not everywhere constant.
The advantages of such a projection used to produce 3-D maps are many. The most evident advantage is the ability of the viewer to move up and down, backwards and forwards, and right and left about the map without the perception of overwhelming distortion. Because the map appears distortion free from no one place but, rather, contains very little distortion everywhere, when areas are viewed from a distance proportional to their size, the map may be scrutinized anywhere on its surface from up close or from a distance without the introduction of appreciable distortion. In addition, the vertical exaggeration appears as xe2x80x9cself scaling.xe2x80x9d For example, if the vertical exaggeration is computed to be three times that of actual when viewed at a distance of twelve inches, the vertical exaggeration appears to be six times that of the original when viewed at a distance of twenty-four inches. Therefore, vertical exaggeration is made more pronounced, and hence more noticeable, when the viewer moves further away. Likewise, vertical exaggeration is made less pronounced as the viewer moves in to scrutinize a small area. Such scaling is necessary in the later case to avoid eye strain.
The present invention used for determining the displacement distance of the red and cyan pixels, while computationally complex, produces an image in which perceived pixel elevations are both relatively and absolutely correct. By incorporating the image to be projected into 3-D with a digital elevation model (DEM) which contains or from which can be computed the actual elevation of each pixel in the image, the resulting image accurately represents each pixel at its correct elevation in 3-D. For example, the perception of a mountain rising 1000 meters from the image plane would appear to rise a height equal in elevation to the depth that a canyon cutting 1000 meters into the image plane would appear to descend. As is clear from this example, the present invention, by incorporating a more sophisticated projection algorithm than the prior art, allows for the rendering in the same 3-D image of features which both rise above the image plane, and which descend below it.
In addition, the present invention makes use of a computationally intensive algorithm for determining the location of each red and cyan pixel in the final anaglyph. As mentioned, forward looking algorithms, while simple to implement, often leave gaps in the final image representing losses of data which must be filled. The present invention computes both the red and cyan finished images by considering each pixel in the final images and working backwards to determine which pixel in the original image, draped over the corresponding DEM, and viewed from the appropriate vantage point, would appear as resting at the final location being considered. While considerably more difficult to implement than a forward looking algorithm, the results produced by the present method result in a finished image free from data loss and which do not require smoothing.
In addition, the related art gives no indication of a desire or an ability to produce a composite anaglyph consisting of different images each with a unique DEM. The current implementation allows finished anaglyphs to be combined with additional point, line, area, or image data plotted in varying intensities and constructed from DEMs differing from that of the main image. This ability allows one, for instance, to display mountains in 3-D while making visible, below a planet""s surface, the layout of subterranean coal mines. Similarly, flight paths can be displayed in 3-D overlaid atop the terrain over which the plane will travel. An additional benefit of computing anaglyphs from image and DEM data, as opposed to. the traditional photographic method, is the ability to digitally master the images used to create the anaglyph. For example, digital data such as the contours of geological rock strata may be overlaid on top of satellite data and presented in true 3-D. The resultant anaglyph allows the viewer to vividly perceive the different angles at which rock strata rest and interact with geologic forces.
The present invention is not limited to map data. Each data element of a map occupies a unique position in two dimensions as specified by its latitude and longitude attributes. In addition, the corresponding DEM is comprised of elevations representing deviations from a point of zero elevation (which on earth is usually chosen to be sea level). However, the present invention can be applied to any image each pixel of which possesses a unique position in two dimensions. For example, the x and y image pixel locations of each pixel comprising a CAT scan could be combined with elevation data corresponding to the y displacement of each pixel from a chosen baseline to produce a 3-D image of a body structure.
In addition, the present invention is not limited to an anaglyphic mode of presentation. Left and right views of a full color image may be computed using the algorithm of the present invention and displayed in alternating and near simultaneous fashion to opposing eyes so as to produce the sensation of binocular tree-dimensionality.
Accordingly, one aspect of the invention is directed to a method of combining digital image data with digital elevation data to produce two separate images said separate images, when viewed one with the left eye and the other with the right eye, producing the sensation of binocular three-dimensionality, comprising the steps of:
(a) combining said digital image data with said digital elevation data to create a right eye view image with each pixel in said right eye view image corresponding to the pixel in said digital image data which would appear in three dimensions to reside at the location of said right eye view image pixel were each of said digital image data pixels to reside upon the surface defined by said digital elevation data, observed individually directly from above, from a uniform height and eye separation, projected upon a plane of uniform height;
(b) combining said digital image data with said digital elevation data to create a left eye view image with each pixel in said left eye view image corresponding to the pixel in said digital image data which would appear in three dimensions to reside at the location of said left eye view image pixel were each of said digital image data pixels to reside upon the surface defined by said digital elevation data, observed individually directly from above, from said uniform height and eye separation, and projected upon said plane of uniform height; and
(c) displaying said left eye view image and said right eye view image so as to produce the sensation of binocular three-dimensionality.
Another aspect of the invention is directed to the aforementioned method wherein said left eye view image and said right eye view image are not each comprised of a representation of each individual pixel present in said digital image data arising from the effects of occlusion of said pixels when said digital image data is viewed in combination with said digital elevation data.
Yet another aspect of the invention is directed to the aforementioned method wherein the digital image data is preprocessed into a gray image each pixel of which contains equal amounts of red, blue and green, said gray image being subsequently combined with said digital elevation to create and display said left eye view image and said right eye view image.
Still another aspect of the invention is directed to the aforementioned method wherein an anaglyph is formed from said left eye view image and said right eye view image comprising the steps of:
(a) assigning each pixel in said left eye view image a single hue;
(b) assigning each pixel in said right eye view image a single hue which is orthogonal to said single hue assigned to each pixel in said left eye view image; and
(c) assigning each pixel in said anaglyph the sum of the red, blue, and green values present in each corresponding pixel from both the left eye view image and the right eye view image.
Yet another aspect of the invention is directed to the aforementioned method wherein said single orthogonal hues consist of the pairs red and cyan, green and blue, and red and blue..
Yet another aspect of the invention is directed to the aforementioned method wherein said left eye view images and said right eye view images are displayed on a surface in a manner comprising the steps of:
(a) displaying said left eye view image on the surface in a manner so as to be perceivable by only the viewer""s left eye;
(b) displaying said right eye view image on the surface in rapid succession with (a) in a manner so as to be perceivable by only the viewer""s right eye; and
(c) continuously repeating in an alternating fashion steps (a) and (b).
Another aspect of the invention is directed to the aforementioned method wherein each of said left eye view images is comprised of multiple separate left eye view images and each of said right eye view images is comprised of multiple separate right eye view images combined in a manner comprising the steps of:
(a) computing multiple separate said left and right eye view images each covering an area which intersects in whole or in part with that of at least one other separate said left or right view image;
(b) assigning a multiplier between 0 and 1 to each separate said left or right eye view image corresponding to the desired opacity of each separate said view image;
(c) applying the corresponding multiplier to each pixel of each of said separate view images; and
(d) adding each corresponding pixel value from each separate left or right view image to form one each of final said left and right eye view images.
Yet another aspect of the invention is directed to the immediately preceding aspect wherein each of said left and right view images are perceived as consisting of multiple layers of three-dimensional images, each of said layers being partially, fully, or not at all transparent with respect to other said layers of three-dimensional images.
Yet another aspect of the invention is directed to the aforementioned method wherein each row of the right eye view image is created by projecting a single row of said digital image data in conjunction with a single row of said digital elevation data while proceeding from left to right across said row of digital elevation data.
Yet another aspect of the invention is directed to the aforementioned method wherein each row of the left eye view image is created by projecting a single row of said digital image data in conjunction with a single row of said digital elevation data while proceeding from right to left across said row of digital elevation data.
Yet another aspect of the invention is directed to the aforementioned method wherein said digital elevation data is comprised of at least two values which differ in magnitude.
An additional aspect of the invention is directed to an image comprising a plurality of pixels each of said pixels having an intensity of a first hue and an intensity of an orthogonal second hue wherein when viewed with apparatus which admits the first hue to a viewer""s right eye and admits the second hue to the viewer""s left eye, the image is perceived to be three-dimensional with each of said pixels projected as though viewed from directly above, with a uniform eye separation, and a uniform height.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.